package org.example.sward.tooffer;

import javax.swing.*;
import java.lang.invoke.WrongMethodTypeException;
import java.lang.management.BufferPoolMXBean;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/2/11 15:51
 */
public class Offer12 {

    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};

    public static void main(String[] args) {
        Offer12 offer12 = new Offer12();
        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "ABCCED";


       boolean result = offer12.exist(board,word);
        System.out.println(result);
    }

    public boolean exist(char[][] board,String word){
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++) {
                if(dfs(board,words,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * dfs遍历
     * @param board 棋盘
     * @param words 单词
     * @param i
     * @param j
     * @param k
     * @return
     */
    private boolean dfs(char[][] board, char[] words, int i, int j, int k) {
        //递归的终止条件
         if(i >= board.length || i < 0 ||j >= board[0].length || j < 0 || board[i][j] != words[k]){
            return false;
        }
        //如果长度相等，说明找到了
        if(k == words.length - 1){
            return true;
        }
        board[i][j] = '\0';

        boolean res = dfs(board,words,i+1,j,k+1) || dfs(board,words,i-1,j,k+1) ||dfs(board,words,i,j+1,k+1) || dfs(board,words,i,j-1,k+1);
        //还原状态
        board[i][j] = words[k];
        return res;

    }

}
